/*
 * @Author: liusheng
 * @Date: 2022-06-05 22:29:11
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-05 22:55:52
 * @Description: 剑指 Offer II 073. 狒狒吃香蕉
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 073. 狒狒吃香蕉
狒狒喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。

狒狒可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉，下一个小时才会开始吃另一堆的香蕉。  

狒狒喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

 

示例 1：

输入：piles = [3,6,7,11], h = 8
输出：4
示例 2：

输入：piles = [30,11,23,4,20], h = 5
输出：30
示例 3：

输入：piles = [30,11,23,4,20], h = 6
输出：23
 

提示：

1 <= piles.length <= 104
piles.length <= h <= 109
1 <= piles[i] <= 109
 

注意：本题与主站 875 题相同： https://leetcode-cn.com/problems/koko-eating-bananas/

通过次数10,950   提交次数20,885
 */

/*
binary search solution
*/
#include "header.h"
class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int maxPile = INT_MIN;
        for (auto pile: piles)
        {
            if (pile > maxPile)
            {
                maxPile = pile;
            }
        }

        if (piles.size() == h)
        {
            return maxPile;
        }

        int first = 1;
        int iter = 0;
        int step = 0;
        int count =  maxPile;
        int eatTime = 0;
        while (count > 0)
        {
            iter = first;
            step = count / 2;
            iter += step;

            eatTime = caculateEatTime(piles,iter);
            if (eatTime > h)
            {
                first = ++iter;
                count -= (step + 1);
            }
            else
            {
                count = step;
            }
        }

        return first;   
    }
private:
    // 返回狒狒以速度 speed吃完所有香蕉需要的时间
    int caculateEatTime(const vector<int> & piles,int speed)
    {
        int time = 0;
        for (auto pile : piles)
        {
            time += pile / speed;
            time += pile % speed ? 1 : 0;
        }

        return time;
    }
};

/*
same as above,use std::max_element to caculate the max pile
*/
class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        auto maxPileIter = std::max_element(piles.begin(),piles.end());
        
        int first = 1;
        int step = 0;
        int iter = 0;
        int count = *maxPileIter;
        
        int eatTime = 0;
        while (count > 0)
        {
            iter = first;
            step = count / 2;
            iter += step;
            
            eatTime = totalEatTime(piles,iter);
            if (eatTime > h)
            {
                first = ++iter;
                count -= (step + 1);
            }
            else
            {
                count = step;
            }
        }
        
        return first;
    }
private:
    //eat at speed k,caculate the total time for eat all piles
    int totalEatTime(const vector<int>& piles,int k)
    {
        int time = 0;
        for (auto pile : piles)
        {
            time += pile / k;
            time += pile % k ? 1 : 0;
        }
        return time;
    }
};